package offerbook;

import java.util.ArrayList;

/**
 * Created at 2019/11/1 0001 下午 5:03
 * 输出所有和为S的连续正数序列。
 * 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
 * 如S = 15，输出1~5，4~6,7~8
 * 利用{@link Code41_FindSumInArray#findSum2(int[], int)}思想。
 * 一开始初始化设定集合为{1,2},集合的头和尾只增不减。
 * 当集合的和小于S，说明需要从集合尾部增加元素。
 * 当集合的和大于S，说明需要从集合头部删除元素。
 * <p>
 * S= 15,集合从{1,2}  - {1,2,3,4}均小于15.
 * {1,2,3,4,5} = 15
 * {1,2,3,4,5,6} > 15,那么添加任意 0<num<集合头部,会导致更大，所以头部只能往前。
 * {2,3,4,5,6} > 15，任意添加0<num<2,会导致更大，头部只能往前。
 * {3,4,5,6} > 15，任意添加0<num<3,会导致更大，头部只能往前。
 * {4,5,6} = 15
 * {5,6} < 15 ,1-4已经被添加过了，不能再重复去回头添加，要去往后添加。
 * {5,6,7} > 15,任意添加1-4会更大，所以集合只能缩减。
 * {6,7} < 15
 * {6,7,8} > 15
 * {7,8} = 15
 * <p>
 * 终止条件。因为集合是连续的，并且元素至少是两个，所以当集合较小的元素 >= (sum+1)/2，肯定后面的都不符合。
 */
public class Code41_FindSumInArray1 {

    /**
     * 通过：
     */
    public static ArrayList<ArrayList<Integer>> findSum1(int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //至少是{1,2}
        if (sum <= 2) {
            System.out.println("找不到");
            return res;
        }
        int small = 1;
        int big = 2;
        list.add(small);
        list.add(big);
        //求和，利用等差数列，从ArrayList中拿，是O(1)。
        int curSum = 0;
        while (big <= (sum + 1) / 2) {
            //(a1+an)*n/2;
            curSum = (list.get(0) + list.get(list.size() - 1)) * list.size() / 2;
            if (curSum < sum) {
                list.add(++big);
            } else if (curSum > sum) {
                //只要删除第一个元素
                list.remove(0);
            } else {
                res.add(new ArrayList<>(list));
                //再把集合扩大，不然big不变，会死循环
                list.add(++big);
            }
        }
        return res;
    }


    public static void findSum2(int sum) {
        //至少是{1,2}
        if (sum <= 2) {
            System.out.println("找不到");
            return;
        }
        int small = 1;
        int big = 2;
        //求和，利用等差数列，从ArrayList中拿，是O(1)。
        int curSum = 0;
        while (big <= (sum + 1) / 2) {
            //(a1+an)*n/2;
            curSum = (small + big) * (big - small + 1) / 2;
            if (curSum < sum) {
                big++;
            } else if (curSum > sum) {
                //只要删除第一个元素
                small++;
            } else {
                for (int i = small; i <= big; i++) {
                    System.out.print(i + ",");
                }
                System.out.println();
                //再把集合扩大，不然big不变，会死循环
                big++;
            }
        }

    }


    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> res = findSum1(15);
        for (ArrayList<Integer> list : res) {
            list.forEach(i -> System.out.print(i + ","));
            System.out.println();
        }
        findSum2(15);
    }


}
